2019 Multi-University Training Contest 3

Diposting di

1004.(二分加线段树DP)

因为二分的值越大 约束条件越少 所以满足二分的性质

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
#define bug cout<<"hehe"<<endl;
int n,k;
ll a[maxn];
ll dp[maxn<<2];
#define ls o<<1
#define rs o<<1|1
void push(int o){
    dp[o]=max(dp[ls],dp[rs]);
}
void build(int o,int l,int r){
    if(l==r){
        dp[o]=-1e18;return;
    }
    int mid=(l+r)/2;
    build(ls,l,mid);build(rs,mid+1,r);
    push(o);
}
ll query(int o,int l,int r,int ql,int qr){
    if(ql<=l&&qr>=r)return dp[o];
    int mid=(l+r)/2;
    ll res=-1e18;
    if(ql<=mid)res=max(res,query(ls,l,mid,ql,qr));
    if(qr>mid)res=max(res,query(rs,mid+1,r,ql,qr));
    return res;
}
void update(int o,int l,int r,int k,ll val){
    if(l==r){
        dp[o]=val;
        return ;
    }
    int mid=(l+r)/2;
    if(k<=mid)update(ls,l,mid,k,val);
    else update(rs,mid+1,r,k,val);
    push(o);
}
ll sum[maxn];
map<ll,int>mp;
map<ll,int>mpp;
vector<ll>ve;
bool check(ll mid){
    build(1,0,n+1);
    int first=lower_bound(ve.begin(),ve.end(),0)-ve.begin();
    update(1,0,n+1,first,0);
    for(int i=1;i<=n;i++){
        int id=mp[sum[i]];
        int ned=lower_bound(ve.begin(),ve.end(),sum[i]-mid)-ve.begin();
      //  cout<<"ned="<<ned<<" "<<sum[i]-mid<<endl;
        ll p=query(1,0,n+1,ned,n+1);
      //  cout<<"p="<<p<<endl;
      //  cout<<"id="<<id<<endl;
        update(1,0,n+1,id,p+1);
      //  cout<<"now query="<<query(1,0,n+1,id,id)<<endl;
        mp[sum[i]]++;
    }
  //  cout<<"query="<<query(1,0,n+1,1,n+1)<<endl;
    if(query(1,0,n+1,0,n+1)>=k){
        return true;
    }
    return false;
}



int main(){
    int t;
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        mp.clear();
        cin>>n>>k;
        ve.clear();
        for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i],ve.push_back(sum[i]);
        ve.push_back(0);
        sort(ve.begin(),ve.end());
        for(int i=0;i<ve.size();i++){
            if(mp.count(ve[i])==0)mp[ve[i]]=i;
        }
        ll l=-2e15,r=2e15,ans;
        mpp=mp;
        while(l<=r){
            ll mid=(l+r)/2;
            mp=mpp;
            if(check(mid)){
                r=mid-1;
                ans=mid;
            }
            else l=mid+1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

1006Fansblog (素数检测 + 威尔逊定理)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+50;
ll mod;
ll P;
ll Q;
int prime[maxn+1];
void getprime(){
    memset(prime,0,sizeof(prime));
    for(ll i=2;i<=maxn;i++){
        if(!prime[i])prime[++prime[0]]=i;
        for(ll j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){
            prime[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}
//****************************************************************
// Miller_Rabin 算法进行素数测试
//速度快，而且可以判断 <2^63的数
//****************************************************************
const int S=20;//随机算法判定次数，S越大，判错概率越小


//计算 (a*b)%c.   a,b都是long long的数，直接相乘可能溢出的
//  a,b,c <2^63
long long mult_mod(long long a,long long b,long long c)
{
    a%=c;
    b%=c;
    long long ret=0;
    while(b)
    {
        if(b&1){ret+=a;ret%=c;}
        a<<=1;
        if(a>=c)a%=c;
        b>>=1;
    }
    return ret;
}

void print(__int128 x)
{
    if(!x)
    {
        puts("0");
        return ;
    }
    string ret="";
    while(x)
    {
        ret+=x%10+'0';
        x/=10;
    }
    reverse(ret.begin(),ret.end());
    cout<<ret<<endl;
}

//计算  x^n %c
long long pow_mod(long long x,long long n,long long mod)//x^n%c
{
    if(n==1)return x%mod;
    x%=mod;
    long long tmp=x;
    long long ret=1;
    while(n)
    {
        if(n&1) ret=mult_mod(ret,tmp,mod);
        tmp=mult_mod(tmp,tmp,mod);
        n>>=1;
    }
    return ret;
}





//以a为基,n-1=x*2^t      a^(n-1)=1(mod n)  验证n是不是合数
//一定是合数返回true,不一定返回false
bool check(long long a,long long n,long long x,long long t)
{
    long long ret=pow_mod(a,x,n);
    long long last=ret;
    for(int i=1;i<=t;i++)
    {
        ret=mult_mod(ret,ret,n);
        if(ret==1&&last!=1&&last!=n-1) return true;//合数
        last=ret;
    }
    if(ret!=1) return true;
    return false;
}

// Miller_Rabin()算法素数判定
//是素数返回true.(可能是伪素数，但概率极小)
//合数返回false;

bool Miller_Rabin(long long n)
{
    if(n<2)return false;
    if(n==2)return true;
    if((n&1)==0) return false;//偶数
    long long x=n-1;
    long long t=0;
    while((x&1)==0){x>>=1;t++;}
    for(int i=0;i<S;i++)
    {
        long long a=rand()%(n-1)+1;//rand()需要stdlib.h头文件
        if(check(a,n,x,t))
            return false;//合数
    }
    return true;
}
__int128 ksm(__int128 a,__int128 b){
    __int128 res=1;
    a%=mod;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
    int t;
   // getprime();
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        ll o;
        cin>>o;
        P=o;
        mod=P;
        for(ll i=P-1;;i--){
            if(Miller_Rabin(i)){
                Q=i;
                break;
            }
        }
        __int128 ans=(-1+mod)%mod;
        for(ll i=P-1;i>Q;i--){
            ans=ans*ksm(i,mod-2)%mod;
        }
        ll u=ans;
        cout<<u<<endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e7+50;
ll mod;
ll P;
ll Q;
int prime[maxn+1];
void getprime(){
    memset(prime,0,sizeof(prime));
    for(ll i=2;i<=maxn;i++){
        if(!prime[i])prime[++prime[0]]=i;
        for(ll j=1;j<=prime[0]&&prime[j]<=maxn/i;j++){
            prime[prime[j]*i]=1;
            if(i%prime[j]==0)break;
        }
    }
}
bool ok(ll x){
    for(int i=1;i<=prime[0];i++){
        if(x%prime[i]==0)return false;
    }
    return true;
}
__int128 ksm(__int128 a,__int128 b){
    __int128 res=1;
    a%=mod;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
    int t;
    getprime();
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        ll o;
        cin>>o;
        P=o;
        mod=P;
        for(ll i=P-1;;i--){
            if(ok(i)){
                Q=i;
                break;
            }
        }
        __int128 ans=(-1+mod)%mod;
        for(ll i=P-1;i>Q;i--){
            ans=ans*ksm(i,mod-2)%mod;
        }
        ll u=ans;
        cout<<u<<endl;
    }
    return 0;
}

1007Find the answer (简单线段树操作)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;

ll a[maxn];
ll tot[maxn];
ll sum[maxn<<2];
ll num[maxn<<2];
#define ls o<<1
#define rs o<<1|1
void push(int o){
    sum[o]=sum[ls]+sum[rs];
    num[o]=num[ls]+num[rs];
}
void build(int o,int l,int r){
    if(l==r){
        sum[o]=0;
        num[o]=0;
        return;
    }
    int mid=(l+r)/2;
    build(ls,l,mid);build(rs,mid+1,r);
    push(o);
}
bool update(int o,int l,int r,int k,ll val){
    if(l==r){
        sum[o]=val;
        num[o]=1;
        return true;
    }
    int mid=(l+r)/2;
    if(k<=mid)update(ls,l,mid,k,val);
    else update(rs,mid+1,r,k,val);
    push(o);
}
int query(int o,int l,int r,ll val){
   // cout<<"o="<<o<<" l="<<l<<" r="<<r<<" val="<<val<<endl;
    if(l==r){
        return num[o];
    }
    int mid=(l+r)/2;
    int res=0;
    if(sum[rs]==val)return num[rs];
    if(sum[rs]<val){
        res+=num[rs];
        return res+query(ls,l,mid,val-sum[rs]);
    }
    else{
        return query(rs,mid+1,r,val);
    }
}
map<ll,int>mp;
ll b[maxn];
int main(){
    int t;
    std::ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        build(1,1,n);
        for(int i=1;i<=n;i++){
            cin>>a[i];
            tot[i]=tot[i-1]+a[i];
            b[i]=a[i];
        }
        sort(b+1,b+1+n);
        mp.clear();
        for(int i=1;i<=n;i++){
          //  cout<<b[i]<<" ";
            if(!mp.count(b[i]))mp[b[i]]=i;
        }
       // cout<<endl;
        for(int i=1;i<=n;i++){
            int id=mp[a[i]];
            if(tot[i]<=m)cout<<0<<" ";
            else{
               // cout<<"tot[i]-m"<<tot[i]-m<<endl;
                cout<<query(1,1,n,tot[i]-m)<<" ";
            }
            update(1,1,n,id,a[i]);
            mp[a[i]]++;
        }
        cout<<endl;
    }
    return 0;
}